class Solution {//归并排序方法
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        merSort(nums,0,nums.size()-1);
        return nums;
    }
    void merSort(vector<int>&nums,int l,int r)
    {
        if(l>=r) return;
        int mid=(r+l)>>1;
        merSort(nums,l,mid);
        merSort(nums,mid+1,r);
        //合并数组
        int cur1=l,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=r)
            tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];
        //处理完没有遍历完的数组
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=r) tmp[i++]=nums[cur2++];
        //还原
        for(int i=l;i<=r;i++)
        {
            nums[i]=tmp[i-l];
        }
    }
};
